package symbol;

/**
 * description:
 * author:张腾
 * date:2021-04-03
 */

/**
 * 符号表 用链表实现
 * @param <Key> 键
 * @param <Value> 值
 */
public class SymbolTable<Key,Value> {
    private Node head;
    private int N;

    private class Node{
        public Key key;  //键
        public Value value;  //值
        public Node next;  //下一个节点

        public Node(Key key,Value value,Node next){
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    public SymbolTable(){
        this.head = new Node(null,null,null);
        this.N = 0;
    }

    //获取符号表键值对的个数
    public int size(){
        return N;
    }

    //往符号表插入键值对
    public void put(Key key,Value value){
        //符号表已存在键为key的键值对，那么只需要找到该键值对，替换value值
        Node n = head;
        while(n!=null){
            n = n.next;
            if (n.value.equals(value)){
                n.value = value;
                return;
            }
        }

        //如果符号表中不存在键为key的键值对，则创建新的节点，保存要插入的键值对，把新结点插入链表的头部的后面，head.next = 新节点
        Node newNode = new Node(key,value,null);
        Node oldFirst = head.next;
        head.next = newNode;
        newNode.next = oldFirst;

        N++;
    }

    //删除符号表中键为key的键值对
    public void delete(Key key){
        Node n = head;
        while(n!=null){
            if (n.next.key.equals(key)){
                n.next = n.next.next;
                N--;
                return;
            }

            n = n.next;
        }
    }

    //从符号表中获取key对应的值
    public Value get(Key key){
        Node n = head;
        while (n.next!=null){
            n = n.next;
            if (n.key.equals(key)){
                return n.value;
            }
        }
        return null;
    }

}
